/*
实验6-1 是不是堆
分数 30
作者 陈越
单位 浙江大学

给定一个完全二叉树的层序遍历序列，请判断该二叉树是否是二叉堆。
输入格式：

每组测试第 1 行包含 2 个正整数：m (≤100) 是二叉树的个数；n（1<n≤1000）是每个二叉树中结点的个数。随后 m 行，每行给出 n 个不重复的整数键值（均在 32 位整型 int 范围内），是一个完全二叉树的层序遍历序列。
输出格式：

对每个输入中给定的二叉树，如果其对应了一个最大堆，则在一行中输出 Max Heap；如果对应最小堆，则输出 Min Heap；否则输出 Not Heap。随后在下一行输出这棵树的后序遍历序列。一行中的数字间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：

3 8
98 72 86 60 65 12 23 50
8 38 25 58 52 82 70 60
10 28 15 12 34 9 8 56

输出样例：

Max Heap
50 60 65 72 12 23 86 98
Min Heap
60 58 52 38 82 70 25 8
Not Heap
56 12 34 28 9 8 15 10
*/

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

void postOrder(vector<int> &tree, int root, bool &first) {
    if (root >= tree.size()) {
        return;
    }
    postOrder(tree, 2*root+1, first);
    postOrder(tree, 2*root+2, first);
    cout << (first ? "" : " ") << tree[root];
    first = false;
}

int main() {
    int m, n;
    cin >> m >> n;
    for (int i = 0; i < m; i++) {
        vector<int> tree(n);
        for (int j = 0; j < n; j++) {
            cin >> tree[j];
        }
        bool isMaxHeap = true, isMinHeap = true;
        for (int j = 0; j < n; j++) {
            if (2*j+1 < n && tree[j] < tree[2*j+1]) {
                isMaxHeap = false;
            }
            if (2*j+2 < n && tree[j] < tree[2*j+2]) {
                isMaxHeap = false;
            }
            if (2*j+1 < n && tree[j] > tree[2*j+1]) {
                isMinHeap = false;
            }
            if (2*j+2 < n && tree[j] > tree[2*j+2]) {
                isMinHeap = false;
            }
        }
        if (isMaxHeap) {
            cout << "Max Heap" << endl;
        } else if (isMinHeap) {
            cout << "Min Heap" << endl;
        } else {
            cout << "Not Heap" << endl;
        }
        bool first = true;
        postOrder(tree, 0, first);
        cout << endl;
    }
    return 0;
}